package q1106_parseBoolExpr;

public class Solution_1 {
    /*
    解析布尔表达式
    dfs
     */
    public boolean parseBoolExpr(String expression) {
        // 递归终点
        if (expression.length() == 1) return expression.equals("t");
        // 非运算，去掉外层括号，对计算结果取反
        if (expression.charAt(0) == '!') return !parseBoolExpr(expression.substring(2, expression.length() - 1));
        boolean isAnd = expression.charAt(0) == '&';// 用isAnd标志进行的是&还是|
        boolean ans = isAnd;
        int depth = 0;
        int beg = 2;
        for (int now = 2; now < expression.length() - 1; ++now) {
            depth += expression.charAt(now) == '(' ? 1 : expression.charAt(now) == ')' ? -1 : 0;
            // 深度为0，且下一个字符为,或)，截取子表达式，计算并更新ans和beg
            if (depth == 0 && (expression.charAt(now + 1) == ',' || expression.charAt(now + 1) == ')')) {
                boolean child = parseBoolExpr(expression.substring(beg, now + 1));
                ans = isAnd ? (ans & child) : (ans | child);
                beg = now + 2;// 更新beg，要跳过下一个字符
            }
        }
        return ans;
    }
}
